package com.huang.leetcode;

import com.sun.glass.ui.Size;

import java.util.*;

/**
 * @Author：CreateSequence
 * @Date：2020-07-23 17:12
 * @Description：<描述>
 */
public class app {

    public static void main(String[] args) {
        int n = 5;
        int m = 5;
        int[] u = {1, 2, 3, 3};
        int[] v = {2, 3, 4, 5};
        int[] x = {1, 2, 3, 4, 5};
        int[] y = {1, 1, 1, 1, 1};
        int[] z = {1, 2, 3, 4, 5};

        //int n = 5;
        //int m = 5;
        //int[] u = {1, 2, 3, 3};
        //int[] v = {2, 3, 4, 5};
        //int[] x = {3, 2, 2, 3, 4};
        //int[] y = {1, 2, 2, 1, 2};
        //int[] z = {4603, 2381, 9894, 1537, 6297};

        //int n = 5;
        //int m = 2;
        //int[] u = {1, 2, 3, 3};
        //int[] v = {2, 3, 4, 5};
        //int[] x = {2, 5};
        //int[] y = {2, 2};
        //int[] z = {1, 1};

        for (int i : solve(n, m, u, v, x, y, z)) {
            System.out.print(i + " ");
        }

        String test_string_name;

    }

    /**
     * 扩散II
     * @param n 工厂数量
     * @param m 污染发生次数
     * @param u 工厂u
     * @param v 工厂v
     * @param x 发生污染的工厂
     * @param y 污染范围
     * @param z 污染指数
     * @return
     */
    public static int[] solve(int n, int m, int[] u, int[] v, int[] x, int[] y, int[] z) {
        //初始化各工厂污染指数
        int[] res = new int[n];
        res = Arrays.copyOf(res, n);

        //获取树二维数组，一维表示节点，二维表示节点的子节点
        Integer[][] tree = new Integer[n][n - 1];
        for (int i = 0; i != n - 1; i++) {
            tree[u[i] - 1][i] = v[i] - 1;
            tree[v[i] - 1][i] = u[i] - 1;
        }

        //创建队列
        List<Integer> queue = new ArrayList<>();

        //遍历发生污染的工厂
        for (int i = 0; i < m; i++) {

            //将工厂添加至队列
            queue.add(x[i] - 1);
            //获取污染范围,如果范围大于路径和即默范围为所有工厂
            int yi = y[i] > n - 1 ? n - 1 : y[i];
            //获取污染指数
            int zi = z[i];

            //记录被某次污染中被污染的工厂
            Map<Integer, Integer> map = new HashMap<>(n);
            System.out.println("工厂" + x[i] + "发生污染！" + "污染范围：" + yi + ",污染指数：" + zi + "-----------");

            while (yi-- >= 0) {

                int size = queue.size();

                System.out.println("第" + (yi + 1) + "层，size：" + size);
                //queue.forEach(s -> System.out.println(s));

                for (int j = 0; j < size; j++) {
                    //获取队列第一个
                    int xi = queue.remove(0);

                    //判断工厂是否已经被污染
                    if (map.containsKey(xi)) {
                        continue;
                    }
                    //否则记录工厂，并且为工厂添加污染指数
                    map.put(xi, 0);
                    res[xi] = res[xi] + zi;

                    //获取相连工厂
                    if (tree[xi] == null) {
                        continue;
                    }
                    //将相连工厂加入队列
                    for (int k = 0; k < tree[xi].length; k++) {
                        if (tree[xi][k] != null && !map.containsKey(tree[xi][k])) {
                            queue.add(tree[xi][k]);
                            System.out.println(tree[xi][k]);
                        }
                    }
                    System.out.println();
                }

            }

        }

        return res;
    }

}
